Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.
Implement the MaxStack class:
MaxStack()Initializes the stack object.void push(int x)Pushes elementxonto the stack.int pop()Removes the element on top of the stack and returns it.int top()Gets the element on the top of the stack without removing it.int peekMax()Retrieves the maximum element in the stack without removing it.int popMax()Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.
Example 1:
Input ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] Output [null, null, null, null, 5, 5, 1, 5, 1, 5] Explanation MaxStack stk = new MaxStack(); stk.push(5); // [5] the top of the stack and the maximum number is 5. stk.push(1); // [5, 1] the top of the stack is 1, but the maximum is 5. stk.push(5); // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one. stk.top(); // return 5, [5, 1, 5] the stack did not change. stk.popMax(); // return 5, [5, 1] the stack is changed now, and the top is different from the max. stk.top(); // return 1, [5, 1] the stack did not change. stk.peekMax(); // return 5, [5, 1] the stack did not change. stk.pop(); // return 1, [5] the top of the stack and the max element is now 5. stk.top(); // return 5, [5] the stack did not change.
Constraints:
-107 <= x <= 107- At most
104calls will be made topush,pop,top,peekMax, andpopMax. - There will be at least one element in the stack when
pop,top,peekMax, orpopMaxis called.
Follow up: Could you come up with a solution that supports
O(1) for each top call and O(logn) for each other call? Average Rating: 3.42 (76 votes)
Approach #1: Two Stacks [Accepted]
Intuition and Algorithm
A regular stack already supports the first 3 operations, so we focus on the last two.
For peekMax, we remember the largest value we've seen on the side. For example if we add [2, 1, 5, 3, 9], we'll remember [2, 2, 5, 5, 9]. This works seamlessly with pop operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.
For popMax, we know what the current maximum (peekMax) is. We can pop until we find that maximum, then push the popped elements back on the stack.
Our implementation in Python will showcase extending the list class.
Complexity Analysis
-
Time Complexity: O(N) for the
popMaxoperation, and O(1) for the other operations, where N is the number of operations performed. -
Space Complexity: O(N), the maximum size of the stack.
Approach #2: Double Linked List + TreeMap [Accepted]
Intuition
Using structures like Array or Stack will never let us popMax quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making popMax faster than O(N) time complexity.
Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in O(1) time.
We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in O(logN) time.
Algorithm
Let's store the stack as a double linked list dll, and store a map from value to a List of Node.
-
When we
MaxStack.push(x), we add a node to ourdll, and add or update our entrymap.get(x).add(node). -
When we
MaxStack.pop(), we find the valueval = dll.pop(), and remove the node from ourmap, deleting the entry if it was the last one. -
When we
MaxStack.popMax(), we use themapto find the relevant node tounlink, and return it's value.
The above operations are more clear given that we have a working DoubleLinkedList class. The implementation provided uses head and tail sentinels to simplify the relevant DoubleLinkedList operations.
A Python implementation was not included for this approach because there is no analog to TreeMap available.
Complexity Analysis
-
Time Complexity: O(logN) for all operations except
peekwhich is O(1), where N is the number of operations performed. Most operations involvingTreeMapare O(logN). -
Space Complexity: O(N), the size of the data structures used.
Last Edit: February 21, 2019 2:11 PM
I don't think I can write 80 lines of code in the interview. So I will be the candidate who cannot find the optimal solution for an easy level question.
February 5, 2020 6:57 PM
Why this question is marked Easy? In my view, it is even harder than many Medium questions.
Obviously, the first solution is more interview-friendly.
June 19, 2019 1:52 AM
When you come up with an O(N) solution ( similar to the 1st solution) in an interview, it is likely to get a followed up question like "can you improve the performance?", so you will need to at least know how to use TreeMap to tackle this type of problem. After a few hints, you finally know you will use doubly linkedlist...In my mind, this is a at least Medium Difficulty level problem. But anyway, practice makes perfect. We really need to stop complaining but spend more time on more problems. cheers.
April 11, 2020 7:38 AM
This should be a medium level question I believe, the explanation of the solution is very good. Thank You @awice for your contributions to the LC community.
In first Solution, I feel there is something wrong with popMax algorithm.
It will result in unequal number in maxStack in case of 3, 5, 1 as an input.
I think this problem is a very good exercise for interviews because it helps you showcase your time complexity skills and trade-offs versus spitting out the most optimized version. If a candidate tells me that the goal is to reduce the time complexity of popMax, that alone is a positive signal. If you manage to come up with solution 2 verbally, it's a very good signal. If you actually code solution 2 in 15 minutes, I'd know you've seen it on LC :)
December 12, 2019 8:55 PM
Approach #1 Python solution is broken. You cannot compare None with an int so the push method should be replaced with:
def push(self, x):
m = max(x, self[-1][1] if self else float("-inf"))
self.append((x, m))
But even then, the algorithm fails for input:
["MaxStack","push","push","popMax","peekMax"]
[[],[5],[1],[],[]]
Cmon, I thought this was an "easy" question!
December 30, 2017 11:39 AM
How do you handle duplicates for approach 2?
Last Edit: February 4, 2020 10:02 PM
First solution is wrong. push(5), push (1) and then popMax(), then maxstack is empty. Ideally maxstack should have value 1
x
class MaxStack {public: list<int> v; map<int, vector<list<int>::iterator>> mp; MaxStack() { } void push(int x) { v.insert(v.begin(), x); mp[x].push_back(v.begin()); } int pop() { int x = *v.begin(); mp[x].pop_back(); if (mp[x].empty()) mp.erase(x); v.erase(v.begin()); return x; } int top() { return *v.begin(); } int peekMax() { return mp.rbegin()->first; } int popMax() { int x = mp.rbegin()->first; auto it = mp[x].back(); mp[x].pop_back(); if (mp[x].empty()) mp.erase(x); v.erase(it); return x; }};